package cn.zifangsky.random.questions;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 蓄水池抽样算法
 *
 * <p>有一台机器按自然数序列的方式吐出球（1号球，2号球，3号球，……），你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。
 * 设计一种选择方式，使得当机器吐出第N号球的时候（N＞K），袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个被选进袋子的概率都是K/N。
 *
 * 举一个更具体的例子，有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10个球，并且1～100号中的每一个球被选中的概率都是10/100。
 * 然后继续吐球，当吐出1000个球时，袋子里有10个球，并且1～1000号中的每一个球被选中的概率都是10/1000。
 * 继续吐球，当吐出i个球时，袋子里有10个球，并且1～i号中的每一个球被选中的概率都是10/i，即吐球的同时，已经吐出的球被选中的概率也动态地变化。</p>
 *
 * @author zifangsky
 * @date 2020/7/7
 * @since 1.0.0
 */
public class Problem_005_ReservoirSampling {
    private final Random rnd = new Random();

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        //吐出100个球，而袋子里只能装10个球
        System.out.println(Arrays.toString(this.reservoirSampling(100, 10)));
    }


    /**
     * 蓄水池抽样算法
     * @author zifangsky
     * @date 2020/7/7 16:59
     * @since 1.0.0
     * @param n 吐出N个球
     * @param k 只有K个球的袋子
     * @return int[]
     */
    private int[] reservoirSampling(int n, int k){
        if(n < 1 || k < 1){
            return null;
        }

        int[] arr = new int[Math.min(n, k)];

        //1. 初始化
        for(int i = 0; i < arr.length; i++){
            arr[i] = i + 1;

        }

        //2. 继续处理吐出的剩下的球
        for(int i = k + 1; i <= n; i++){
            //如果满足概率：k/i
            if(this.random(i) <= k){
                //则随机替换数组中的某个数字
                arr[this.random(k) - 1] = i;
            }
        }

        return arr;
    }

    /**
     * 随机返回 1~max 的整数
     */
    private int random(int max){
        return rnd.nextInt(max) + 1;
    }
}
